/*************************************************************************
 * File Name:    Word_Break_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sun 27 Oct 2013 12:28:12 AM CST
 * 
 * Description:  
 |--------------------------------------------------------------------------
 | Problem: Word Break II
 |
 | Given a string s and a dictionary of words dict, add spaces in s to
 | construct a sentence where each word is a valid dictionary word.
 |
 | Return all such possible sentences.
 |
 | For example, given
 | s = "catsanddog",
 | dict = ["cat", "cats", "and", "sand", "dog"].
 |
 | A solution is ["cats and dog", "cat sand dog"].
 |
 |------------------------------------------------------------------------
 |
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
private:
    vector<string> ans;
    
    void dfs(const vector<vector<string> > &pre, size_t p, string ts)
    {
        if (p == 0) {
            ans.push_back(ts);
            return;
        }
        
        for (size_t i = 0; i < pre[p].size(); ++i) {
            dfs(pre, p - pre[p][i].size(), p + 1 == pre.size() ? pre[p][i] + ts : pre[p][i] + " " + ts);
        }
    }
    
public:
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        typedef unordered_set<string>::iterator dict_iter_t;
        ans.clear();
        vector<bool> dp(s.size() + 1, false);
        vector<vector<string> > pre(s.size() + 1);
        
        dp[0] = true;
        for (size_t i = 0; i <= s.size(); ++i) {
            if (!dp[i]) continue;
            for (dict_iter_t it = dict.begin(); it != dict.end(); ++it) {
                if (i + it->size() <= s.size() && s.substr(i, it->size()) == *it) {
                    pre[i + it->size()].push_back(*it);
                    dp[i + it->size()] = true;
                }
            }
        }
        if (!dp[s.size()]) return vector<string>();
        dfs(pre, s.size(), "");
        
        return ans;
    }
};
